P2408 不同子串个数

这道题用后缀自动机可以暴力解决。

建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG\text{DAWG}dpdpdp[u]dp[u]表示包含转移uu的子串数量,很容易列出转移式:

dp[u]=vson[u]dp[v]dp[u]=\sum_{v \in son[u]} dp[v]

阅读全文 »

SP8222 NSUBSTR - Substrings

不难发现到f[i]f[i]就是长度为 ii 子串的 endpos|endpos| 的最大值。

根据一个性质后缀自动机的一个点的 endposendpos 被他的后继分为了很多部分,所以我们可以用parent树dp\text{parent树dp},处理出它的endpos|endpos|

接着是统计答案,显然我们可以用线段树覆盖。

阅读全文 »

P3195 [HNOI2008]玩具装箱TOY

这道题像我这样的 dpdp 蒟蒻都能一眼看出 dpdp 式:

sumsumcc 的前缀和,则有

dp[i]=min{dp[j]+((ij1)+(sum[i]sum[j])L)2}  (0j<i)dp[i]=min\{ dp[j]+((i-j-1)+(sum[i]-sum[j])-L)^2 \} ~~ (0 \le j < i)

阅读全文 »

CF487B Strip

一道并不难的 dpdp 题。转移式很好列:

dp[i]=min{dp[j]+1}    (0jil &&max(j+1,i)min(j+1,i)<=s)dp[i]=min\{ dp[j]+1 \} ~~~~ (0 \le j \le i - l~\&\&max(j+1,i)-min(j+1,i)<=s)

阅读全文 »

P3503 [POI2010]KLO-Blocks

首先可以知道一个区间满足条件的必要条件是该区间的平均数大于等于 kk

进一步可以发现这是一个充要条件。因为大于 kk 的数一定能填补到小于 kk 的数。

记一个合法的区间为 [l,r][l,r]sumsumaa 的前缀和。

阅读全文 »

P5496 【模板】回文自动机(PAM)

不懂回文自动机的可以看这篇博客

现在默认大家都懂,用 Cnt[i]Cnt[i] 表示以 ii 结尾的回文串的个数。

由于 Link[i]Link[i] 表示 ii 的最长回文后缀,所以 Cnt[i]=Cnt[Link[i]]+1Cnt[i]=Cnt[Link[i]]+1(加上 ii 点所标示的一个回文串)

阅读全文 »

P3649 [APIO2014]回文串

不懂回文自动机的点这里

如果单纯的记录每个点结束回文串的数量,因为我们用的增量法 ,wwww 只会被计算一次 , 第二个样例都过不了。

所以在构建回文自动机后 , 我们将每一个 Cnt[Link[u]]+=Link[u]Cnt[Link[u]]+=Link[u] , 就可以避免由上述方法带来的影响了。

阅读全文 »

P4555 [国家集训队]最长双回文串

显然是一道回文自动机板题。

L[i]L[i] 表示以 ii 号点为左端点的最长回文串 , R[i]R[i] 表示以 ii 号点为右端点的最长回文串。

L[i]L[i] 可以通过将回文串倒过来建自动机求得 , R[i]R[i] 可以直接用原回文串建自动机求得。

阅读全文 »